Packet switching is employed in communication systems, wherein packets may be transmitted from one router to another across networks or sub-networks. In order to forward traffic, a router may use a routing table to look up the address and egress port of a next hop. Such a routing table may be known as a forwarding information base (FIB), wherein a destination address of a packet may be a key in an FIB.
Upon receiving a packet, the router may perform a network address lookup to find the longest prefix match between the destination address of the packet and a network address prefix and subsequently determine the corresponding outgoing interface. Thus, storing and accessing such information efficiently and intelligently may improve the lookup process, and is thereby a challenging problem in today's networking paradigm.
Trie lookup is a widely used network address lookup technique implemented in a router. A trie may be a tree data structure in which the position of a node in the tree represents a corresponding path key. A node in a trie may represent a longest prefix match (LPM) up to the position of the node, which may be useful in representing network address prefixes in an FIB. The trie lookup technique may be further improved with a multi-bit trie that examines multiple bits for a network address lookup. Multi-bit trie based algorithms may be achieved through pipelined trie levels or stages; however, the number of network address prefixes located on different trie stages may sometimes be heavily unbalanced, resulting in low memory utilization for stages which have less prefixes. Consequently, there may be a need to balance trie stages and corresponding memories in order to improve efficiency in network address lookup operations.